package main

import (
	"fmt"
)

func main() {
	arr := []int{2, 4, 5, 67, 4, 3, 25, 6, 8, 4}
	quickSort2(arr)
	fmt.Println(arr)
}

func quickSort2(arr []int) {
	if arr == nil && len(arr) < 1 {
		return
	}

	process2(arr, 0, len(arr)-1)
}

func process2(arr []int, L, R int) {

	if L == R || L > R {
		return
	}

	ints := sortt(arr, L, R)

	process2(arr, L, ints[0]-1)
	process2(arr, ints[1]+1, R)
}

func sortt(arr []int, L, R int) []int {

	if L > R {
		return []int{-1, -1}
	}

	if L == R {
		return []int{L, R}
	}

	less := L - 1
	more := R
	index := L
	for index < more {
		if arr[index] < arr[R] {
			less++
			arr[index], arr[less] = arr[less], arr[index]
			index++
		} else if arr[index] == arr[R] {
			index++
		} else if arr[index] > arr[R] {
			more--
			arr[index], arr[more] = arr[more], arr[index]
		}
	}

	arr[R], arr[more] = arr[more], arr[R]
	return []int{less + 1, more}
}
